1. Field of the Invention
The present invention relates generally to an apparatus, program and method for network communications. More particularly, the present invention relates to a cluster head resignation procedure that minimizes data loss in a communications network having member stations arranged in clusters, with each cluster having a head station.
2. Related Art
Communications networks can be formed by arranging a plurality of mobile communications stations into a hierarchical configuration including groups (e.g., xe2x80x9cclustersxe2x80x9d), with each group having a group or cluster head (e.g., xe2x80x9ccluster gatewayxe2x80x9d). A cluster head represents affiliated cluster members to the network. Cluster head stations communicate with each other to form a network backbone, and cluster member stations relay messages to the network through affiliated cluster heads. In mobile systems, cluster members move into and out of clusters depending on their physical location and radio connectivity. Depending on mobility changes of stations in a mobile network, new clusters form and cluster heads emerge as stations move around.
Wireless communications in a mobile environment has a unique problem in that network topology is constantly changing. As will be appreciated, grouping member stations into clusters addresses this problem since communication nodes outside of a cluster do not need to know about changes of topology within a cluster. Thus, a large amount of changing topology information does not need to be flooded through the network.
An example of a mobile communications network is shown in FIG. 2a. Areas 1a, 1b and 1c represent individual clusters in FIG. 2a. In FIG. 2a, as in the other relevant figures, a double-circle indicates a Cluster Head (xe2x80x9cCHxe2x80x9d), whereas a single circle indicates a Cluster Member (xe2x80x9cCMxe2x80x9d). In the FIG. 2a example, CM2 and CM3 are affiliated with a cluster headed by CH1, and CM6 and CM7 are affiliated with a cluster headed by CH5.
Another example of a mobile communications network is disclosed in U.S. Pat. No. 5,850,592, issued to S. Ramanathan on Dec. 15, 1998, and assigned to the same assignee. The U.S. Pat. No. 5,850,592 discloses a method for a plurality of mobile stations to automatically organize themselves into a hierarchical network, in which some of the stations operate as message gateways (e.g., cluster heads) for a cluster of mobile stations. Initially, mobile stations search for available cluster heads and initiate an affiliation procedure to establish themselves as cluster members. If the affiliation procedure is successful, a mobile station operates as a cluster member. A mobile station monitors its communication link with a cluster head and seeks to reestablish a link when it is compromised or severed. During this reaffiliation, a mobile station may affiliate with a different cluster head if such cluster head is within range. Otherwise, a mobile station promotes itself to operate as a cluster head.
In the arrangement of the U.S. Pat. No. 5,850,592, a plurality of mobile stations is employed, with each station operating in at least two basic modes. In the first mode, the mobile station serves as a message gateway (e.g., a xe2x80x9ccluster headxe2x80x9d or xe2x80x9cnetwork access pointxe2x80x9d) for a cluster of other member stations (e.g., xe2x80x9cnon-gatewayxe2x80x9d stations). The second mode allows the mobile station to operate as a non-gateway (or xe2x80x9ccluster memberxe2x80x9d) station. Each mobile station determines which out of the two modes to operate in, as discussed above.
The mobile stations disclosed in the U.S. Pat. No. 5,850,592 patent can operate at two different power levels. When there are no other available cluster heads, the mobile station operates as a cluster head, and transmits at a relatively high power level. The cluster head transmits at the relatively high power level to communicate with other cluster head stations and to typically provide longer distance network links. Although the cluster head communicates at a higher power level with other cluster heads, the cluster head can still communicate with its cluster members using a relatively lower power level. A cluster head can also periodically broadcast a signal to establish the station""s presence and its availability to operate as a cluster head.
The cluster head stations disclosed in the U.S. Pat. No. 5,850,592 periodically test their proximity conditions to other cluster head stations, e.g., by signal strength measurements or using data available through the cluster head stations exchanging messages. If the tests indicate that the proximity conditions are exceeded, e.g., that the particular station""s operation as a gateway is possibly redundant and/or unnecessary, the station executes a resignation procedure. Before terminating operation as a cluster head, the cluster head broadcasts a termination request and waits for a predetermined time to see if all affiliated cluster members accept the request. Each linked or neighboring cluster head station also receives a resignation request from the resigning cluster head. The receiving cluster head neighbor checks to see if the resigning station is an articulation point. For example, as shown in FIG. 2b, CH5 is an articulation point since it is the only cluster head linking CH1 and CH4. If, on the other hand, as shown in FIG. 2a, CH1 and CH4 are linked independently of CH5, CH5 is not an articulation point for CH1 or CH4. If the resigning cluster head is an articulation point, the receiving cluster head neighbor does not send a confirmation message, essentially blocking the resignation of the cluster head.
This process may not be entirely satisfactory in all settings because the process requires communication between the resigning node and its neighbors as part of the process of attempting to resign. In many cases such communication is not necessary because the resigning cluster head may make this determination itself (e.g., that it is an n-connectivity point) and block its own resignation for that reason. In general, an n-connectivity point is a member of at least one set of xe2x80x98nxe2x80x99 nodes whichxe2x80x94if that set were deleted from the networkxe2x80x94would cause the network to fall into two or more distinct, unconnected portions (e.g., partitions). Thus an xe2x80x9carticulation pointxe2x80x9d is a 1-connectivity point. If a node is a 2-connectivity point, then removal of that node and some other node would partition the network, and so forth. As will be appreciated, it is desirable to have networks remain connected. Hence, in general, it is also desirable to have at least xe2x80x98nxe2x80x99 nodes to connect the various portions of the network, where n greater than 1 for redundancy.
Returning to the resignation procedure discussed in the U.S. Pat. No. 5,850,592, if a resignation is successful, and after a random amount of time has expired, the resigning mobile station must reestablish itself as a cluster member. This resignation process is a xe2x80x9cbreak-before-makexe2x80x9d approach; that is, the resigning cluster head actually loses network connectivity (as a cluster head) before it attempts to regain network connectivity (as a cluster member). This type of approach is not always satisfactory as it is usually highly desirable or even essential for every node in a network to have network connectivity at all times.
Other implementations of clustering methods do not even employ resignation procedures. In these cases, a network eventually has so many cluster heads that routing overhead overwhelms the limited available bandwidth. This routing overhead may produce a communication scheme that functions as if there was no attempt to use clusters to reduce network topology traffic.
These types of problems are not adequately addressed in the art. Thus, there is a need for a flexible communications station in a communications network to reduce routing overhead by determining when and how a cluster and a cluster head are no longer needed in the network. There is also a need for a communications node that will not resign if it is a critical node. There is another need to provide an adaptive, wireless mobile communications station with the ability to minimize data loss as a communication node transitions from operating as a cluster head to operating as a cluster member.
The present invention relates generally to a cluster head resignation procedure to improve routing in mobile networking systems. The improved routing procedure prevents data loss while a cluster head resigns A resigning cluster head maintains a communication link (or maintains an ongoing affiliation) with a neighboring cluster head as the resigning cluster head transitions from operating as a cluster head to operating as a cluster member.
According to the invention, a mobile communications station is provided which communicates among a plurality of mobile stations in a network. Stations within the network are arranged in clusters of communication member stations, with one member station in each cluster being a head station for the cluster. Each member station communicates with the network through one or more cluster head stations. The cluster head stations communicate with other cluster head stations. The mobile station includes a transceiver that transmits signals to and receives signals from mobile stations in the network.
According to one aspect of the invention, the mobile communications station includes a memory and a processor. The memory has network information stored thereon. The processor (i) operates the mobile station as a cluster head station; (ii) resigns the mobile station from operating as a cluster head station; and (iii) maintains affiliation with a cluster head neighbor at least during a period in which the mobile station resigns from operating as a cluster head and commences operating as a cluster member of the cluster head neighbor.
According to another aspect, a mobile communications station includes a processor that controls a transceiver to transmit a signal representing an intention of the mobile station to resign as a cluster head station. The processor determines whether the mobile station is a network n-connectivity point, and prevents the mobile station from resigning as a cluster head station when the mobile station is an n-connectivity point. A determination is based on analyzing network topology information.
According to yet another aspect, a mobile communications station includes a processor that prevents the mobile station from resigning as a cluster head station based on at least one of a resignation command setting indicating that the mobile station should not resign; a predetermined plan for the mobile station and nearby stations that indicate that the mobile station will better serve the network if it does not resign; indications that other, nearby cluster heads are already in the process of resigning; and discovery that some or all of the cluster members affiliated with the mobile station have not reaffiliated with other clusters.
According to still another aspect, network information stored in a memory includes network topology information. The network topology information includes at least one of signal strength, organizational affiliation, number and type of affiliated stations, planned station movement over time, plans for entering radio silence, disruptions of communications caused by jammers, self-interference, or natural terrain, battery power remaining, and so forth.
According to another aspect, a mobile communications station includes a processor that selects a first neighboring cluster head station to maintain affiliation with while resigning as a cluster head station. A selection is made based on at least one of signal strength, organizational affiliation, number of cluster members affiliated with the cluster head station, highest percentage of transmissions received without disruption, fastest communication link speed, least power required for transmissions, a station that is most compatible with a planned movement of the station, an indicator for radio silence in the future, and direction for pointing a directional antenna so as to avoid jammers or natural interference.
According to still another aspect, a mobile communications station includes a processor that controls a transceiver to transmit a signal to a selected first cluster head station requesting a status change from a cluster head station to a cluster member station.
According to yet another aspect, a mobile communications station includes a processor that resigns the mobile station from operating as a cluster head station when the mobile communication station receives an acknowledgement from the first selected cluster head station, while the processor maintains a communication link with the selected first cluster head station.
Still another aspect of the present invention relates to a mobile station having a processor that selects a second neighboring cluster head station to maintain affiliation with when the mobile station does not receive an acknowledgement from the first neighboring cluster head.
According to yet another aspect, a mobile communications station includes a processor that controls the transceiver to send a signal to each affiliated cluster member station signaling the intended resignation of the mobile station as a cluster head station. The processor controls the mobile station to operate as a cluster member station of a cluster headed by the cluster head neighbor once the transceiver has transmitted the signal.
According to one embodiment, a network communications apparatus is provided. The apparatus includes a memory, a processor and a transmitter. The memory stores network information. The processor (i) controls operation of the apparatus to operate as a cluster gateway; (ii) controls the apparatus to resign from operating as a cluster gateway; and (iii) maintains affiliation with a first cluster gateway at least during a period in which the apparatus ends operation as a cluster gateway and commences operation as a cluster member of the first cluster gateway. The transceiver transmits communication messages.
In another embodiment, a method of operating a communications station is provided. The communications station is in a communications system for communication among plural member stations in a network in which member stations are arranged in clusters of communication member stations. One of the member stations is a cluster head. Each member station communicates with the network through an affiliated cluster head station. The cluster head stations communicate with other cluster head stations. A method of operating a communications station includes steps of (i) operating the communications station as a cluster head station; (ii) resigning the communications station from operating as a cluster head station; and (iii) maintaining affiliation with a first neighbor cluster head station while the communications station transitions from operating as a cluster head station to operating as a member station of a cluster headed by the first neighbor cluster head station.
In another embodiment, computer executable code is stored on a computer readable medium. The code is to operate a communications station so as to communicate with a plurality of mobile stations in a network in which stations are arranged in clusters of communication member stations. One member station is a cluster head station for each cluster. Each member station communicates with the network through at least one affiliated cluster head station. The cluster head stations communicate with other cluster head stations. The computer executable code includes: (i) code to operate the communications station as a cluster head station; (ii) code to resign the communications station from operating as a cluster head station; and (iii) code to maintain affiliation with a first neighbor cluster head station at least during a period when the communication station resigns as a cluster head station and commences operation as a member station of a cluster headed by the first neighbor cluster head station.
In still another embodiment, a method that configures a network of stations is provided. The method is employed in a communications system for communication among plural stations in a network in which stations are arranged in clusters of communication member stations with one of the member stations being a head station of the cluster. The cluster head stations communicate with other cluster head stations. A method that configures the network of stations includes the steps of: (i) operating at least a first and a second station of the plural stations as cluster head stations, the first and second stations forming a communications link; (ii) resigning the first station from operating as a cluster head station when a predetermined resignation condition is met; and (iii) maintaining the communication link between the first and second station as the first station transitions from operating as a cluster head station to operating as a cluster member station of a cluster headed by the second cluster head station.
In still another embodiment, a network communications apparatus is provided. The apparatus includes storage means, first control means, second control means, maintaining means and transmitting means. The storage means stores network information. The first control means controls an operation of the apparatus in a cluster gateway mode. The second control means controls the apparatus to resign from operating in the cluster gateway mode. The maintaining means maintains a communication link with a first cluster gateway while the apparatus transitions from operating in the cluster gateway mode to operating in a cluster member mode as a cluster member of a cluster headed by the first cluster head station. The transmitting means transmits communication messages.
These and other objects, features and advantages will be apparent from the following description of the preferred embodiments of the present invention.